package developer.算法.链表.k个一组反转链表;

import java.util.ArrayList;
import java.util.List;

/**
 * 1 2 3 4 5
 * 3.nex = 3.head
 *
 * @author zhangyongkang
 * @time 2025/3/20 16:46
 * @description 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 */
public class KGeYiZuFanZhuanLianbiao {


    public static void main(String[] args) {
        Solution4 solution = new Solution4();

        ListNode tail = new ListNode(5);
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, tail))));
//        ListNode[] reserver = solution.reserver(head, tail);
        ListNode newHead = solution.reverseKGroup(head, 3);
        ListNode current = newHead;
        while (current != null) {
            System.out.println(current.val);
            current = current.next;
        }

    }


    static class Solution4 {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode hair = new ListNode();
            hair.next = head;
            ListNode pre = hair;
            while (head != null) {
                ListNode tail = head;
                for (int i = 0; i < k - 1; i++) {
                    if (tail.next == null) {
                        return hair.next;
                    }
                    tail = tail.next;

                }
                ListNode next = tail.next;

                reserver(head, tail);
                ListNode hh = head;
                head = tail;
                tail = hh;

                pre.next = head;//连接上一个
                tail.next = next;//连接下一个

                pre = tail;
                head = tail.next;//进入下一个循环

            }
            return hair.next;
        }

        // 1 2 3 4 | 5
        private void reserver(ListNode head, ListNode tail) {
            ListNode pre = tail.next;
            ListNode current = head;
            while (pre != tail) {
                ListNode next = current.next;

                current.next = pre;
                pre = current;
                current = next;
            }
        }
    }


    static class Solution3 {
        public ListNode reverseKGroup(ListNode head, int k) {
            //最头部节点  为了解决 第一组的pre 为空的情况
            ListNode hair = new ListNode(0);
            hair.next = head;
            ListNode pre = hair;

            while (head != null) {
                ListNode tail = head;
                for (int i = 0; i < k - 1; i++) {
                    tail = tail.next;
                    if (tail == null) {
                        return hair.next;
                    }
                }

                ListNode next = tail.next;

                //现在获取到了  头部和尾部 对区间内的头部和尾部进行颠倒
                ListNode[] reserver = reserver(head, tail);
                head = reserver[0];
                tail = reserver[1];

                pre.next = head;//连接上一个
                tail.next = next;//连接下一个

                pre = tail;
                head = tail.next;//进入下一个循环
            }
            return hair.next;
        }

        //1 2 3 4 |5
        // pre = 5
        // next = 1.next(2)
        // current.next= pre;
        // pre = current;
        // curren = pre
        private ListNode[] reserver(ListNode head, ListNode tail) {
            ListNode pre = tail.next;
            ListNode current = head;
            while (pre != tail) {
                ListNode next = current.next;
                current.next = pre;
                pre = current;
                current = next;
            }
            return new ListNode[]{
                    tail, head
            };
        }


    }

    /**
     * 提示： 1 2 3 4 5 6
     * 链表中的节点数目为 n
     * 1 <= k <= n <= 5000
     * 0 <= Node.val <= 1000
     * <p>
     * <p>
     * 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
     * <p>
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     * //
     */
//    public static void main(String[] args) {
////        ListNode listNode = reverseKGroup(
////                new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))),
////                3
////        );
//
//        ListNode listNode = reverseKGroup(
//                new ListNode(1, new ListNode(2)),
//                2
//        );
//        if (listNode == null) {
//
//        } else {
//            while (listNode != null) {
//                System.out.println(listNode.val);
//                listNode = listNode.next;
//            }
//        }
//        System.out.println(listNode);
//    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return head;
        }

        List<List<ListNode>> nodeCache = new ArrayList<>();
        boolean ignoreLast = false;
        while (head != null) {
            int current = 1;
            List<ListNode> currentNodes = new ArrayList<>(k);
            for (; current <= k; ) {
                if (head == null) {
                    break;
                }
                currentNodes.add(head);
                head = head.next;
                current++;
            }
            if (current <= k) {
                ignoreLast = true;
                nodeCache.add(currentNodes);
                break;
            } else {
                nodeCache.add(currentNodes);
            }
        }
        for (int i = 0; i < (ignoreLast ? nodeCache.size() - 1 : nodeCache.size()); i++) {
            List<ListNode> listNodes = nodeCache.get(i);
            int left = 0, right = listNodes.size() - 1;
            while (left <= right) {
                ListNode leftNode = listNodes.get(left);
                ListNode rightNode = listNodes.get(right);
                listNodes.set(left, rightNode);
                listNodes.set(right, leftNode);
                left++;
                right--;
            }
        }
        ListNode result = null;
        ListNode current = null;
        for (int i = 0; i < nodeCache.size(); i++) {
            List<ListNode> currentNode = nodeCache.get(i);
            for (int j = 0; j < currentNode.size(); j++) {
                if (current == null) {
                    current = currentNode.get(j);
                    result = current;
                }
                if ((j == currentNode.size() - 1)) {
                    if (i != nodeCache.size() - 1) {
                        current.next = nodeCache.get(i + 1).get(0);
                    } else {
                        current.next = null;
                    }
                } else {
                    current.next = currentNode.get(j + 1);
                }
                current = current.next;
            }

        }
        return result;

    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/solutions/248591/k-ge-yi-zu-fan-zhuan-lian-biao-by-leetcode-solutio/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    static class SolutionOfficial {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode hair = new ListNode(0);
            hair.next = head;
            ListNode pre = hair;

            while (head != null) {
                ListNode tail = pre;

                // 查看剩余部分长度是否大于等于 k
                for (int i = 0; i < k; ++i) {
                    tail = tail.next;
                    if (tail == null) {
                        return hair.next;
                    }
                }


                ListNode nex = tail.next;
                ListNode[] reverse = myReverse(head, tail);
                head = reverse[0];
                tail = reverse[1];
                // 把子链表重新接回原链表
                pre.next = head;
                tail.next = nex;
                pre = tail;
                head = tail.next;
            }

            return hair.next;
        }

        // 1 2 3 4 |5
        /*
         * next = 1.next;
         * 1.next = 5
         * pre  =1 ;
         * p = 2;
         *
         * 2.next
         *
         * 1 2 3 4 | 5
         *next(2)= 1.next
         * 1.next = prev(5);
         * prev = current(2)
         * current = next
         *
         * */
        public ListNode[] myReverse(ListNode head, ListNode tail) {
            ListNode prev = tail.next;
            ListNode p = head;
            while (prev != tail) {
                ListNode nex = p.next;
                p.next = prev;
                prev = p;
                p = nex;
            }
            return new ListNode[]{tail, head};
        }
    }

}
